{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 张子豪 2019-6-23"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 作业 基于关联规则的商品关联挖掘\n",
    "作者： 寒小阳，助教-Andrei"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 作业说明\n",
    "本次的作业一共有5个任务\n",
    "* 任务一：构造 item2id，id2item\n",
    "* 任务二：编写函数items2int(items, num_items) ，用于通过交易数据得到编码 \n",
    "* 任务三：编写is_subset方法，用于判断 sx 是否为 sy 的subset\n",
    "* 任务四：编写support方法，用于计算s在整个transactions中的support\n",
    "* 任务五：利用Apriori算法（使用BFS来实现）来获取频繁集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 请不要修改此单元格.\n",
    "import time\n",
    "\n",
    "# 如下是此次作业需要用到的交易数据\n",
    "transactions = [[\"milk\", \"bread\"], \n",
    "                [\"butter\"], \n",
    "                [\"beer\", \"diapers\"],\n",
    "                [\"milk\", \"bread\", \"butter\"],\n",
    "                [\"bread\"]\n",
    "               ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mapping from items to ids: {'milk': 3, 'diapers': 4, 'butter': 0, 'bread': 2, 'beer': 1}\n",
      "Mapping from ids to items: ['butter', 'beer', 'bread', 'milk', 'diapers']\n"
     ]
    }
   ],
   "source": [
    "## 张子豪\n",
    "# 步骤1： 数据预处理\n",
    "items = set([t for transaction in transactions for t in transaction ])\n",
    "num_items = len(items)\n",
    "\n",
    "# 任务一: 由你来构造 item2id，id2item\n",
    "# 请构造item2id，存放每一个item及其id（i.e. {'butter': 0, 'beer': 1, 'bread': 2, 'milk': 3, 'diapers': 4}）\n",
    "item2id =  {'butter': 0, 'beer': 1, 'bread': 2, 'milk': 3, 'diapers': 4}\n",
    "\n",
    "# 请构造id2item, 存放每一个item (i.e. ['butter', 'beer', 'bread', 'milk', 'diapers'])\n",
    "id2item = ['butter', 'beer', 'bread', 'milk', 'diapers']\n",
    "\n",
    "print(\"Mapping from items to ids:\", item2id)\n",
    "print(\"Mapping from ids to items:\", id2item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Itemset 9 = ['butter', 'milk']\n",
      "Itemset 31=  ['butter', 'beer', 'bread', 'milk', 'diapers']\n",
      "Itemset 0= []\n",
      "Itemset 4= ['bread']\n",
      "Itemset 12= ['bread', 'milk']\n"
     ]
    }
   ],
   "source": [
    "# 请不要修改此单元格\n",
    "# 步骤2: 定义编码交易数据的两个函数 int2items(s, num_items)，items2int(items, num_items)\n",
    "# Tips: 通过编码返回subset （i.e., 9 = 01001 = {diapers, butter}.）\n",
    "\n",
    "def int2items(s, num_items):\n",
    "    items = []\n",
    "    for i in range(num_items):\n",
    "        if s % 2: items.append(id2item[i])\n",
    "        s >>= 1\n",
    "    return items\n",
    "\n",
    "print(\"Itemset 9 =\", int2items(9, num_items))\n",
    "print(\"Itemset 31= \", int2items(31, num_items))\n",
    "print(\"Itemset 0=\", int2items(0, num_items))\n",
    "print(\"Itemset 4=\", int2items(4, num_items))\n",
    "print(\"Itemset 12=\", int2items(12, num_items))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Items ['milk', 'butter'] = 18\n",
      "All transactions in integer representation: [6, 16, 9, 22, 4]\n"
     ]
    }
   ],
   "source": [
    "# 任务二：由你来编写函数items2int(items, num_items) 通过交易数据得到编码\n",
    "# Tips： i.e. items2int([\"milk\", \"butter\"], num_items) 返回 ”01100“ 即 ”12“\n",
    "\n",
    "def items2int(items, num_items):\n",
    "    idx = 0\n",
    "    # START CODE HERE\n",
    "    idx = [0 for i in range(num_items)]\n",
    "    signal = []\n",
    "    for each in items:\n",
    "        signal.append(item2id[each])\n",
    "    for each in signal:\n",
    "        idx[each] = 1\n",
    "    idx = [str(each) for each in idx]\n",
    "    idx = ''.join(idx)\n",
    "    idx = int(idx,2)\n",
    "    return idx\n",
    "\n",
    "print(\"Items ['milk', 'butter'] =\", items2int([\"milk\", \"butter\"], num_items))\n",
    "\n",
    "# 打印所有交易数据的编码\n",
    "int_trans = [items2int(t, num_items) for t in transactions]\n",
    "print(\"All transactions in integer representation:\", int_trans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 张子豪\n",
    "# 步骤3：定义两个帮助方法is_subset 和 support 方法\n",
    "# 任务三：由你来编写is_subset方法，用于判断 sx 是否为 sy 的subset\n",
    "def is_subset(sx, sy):\n",
    "    z = set(sx).issubset(set(sy))\n",
    "    return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 张子豪\n",
    "# 任务4：由你来编写support方法，用于计算s在整个transactions中的support\n",
    "# Tips: 1，有可能用到is_subset方法 \n",
    "#       2，要记得 support 是物品集在所有Transactions中出现的频率\n",
    "def support(s, transactions):\n",
    "    # START CODE HERE\n",
    "    k = 0\n",
    "    for transaction in transactions:\n",
    "        if is_subset(s,transaction):\n",
    "            k += 1\n",
    "    return k/len(transactions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All frequent subsets: [['butter'], ['bread'], ['milk'], ['bread', 'milk']]\n",
      "Time used for mining: 0.0003104209899902344 seconds.\n"
     ]
    }
   ],
   "source": [
    "# 请不要修改此单元格\n",
    "# 步骤4：建模从而获取频繁集\n",
    "# 方法一：直接计算法  \n",
    "# 复杂度: O(2^n).\n",
    "\n",
    "sup = 0.3\n",
    "num_transactions = len(transactions)\n",
    "freq_sets = []\n",
    "start_time = time.time()\n",
    "for i in range(1, 2 ** num_items):\n",
    "    subsets = int2items(i, num_items)\n",
    "    freq = support(subsets, transactions)\n",
    "    if freq > sup: freq_sets.append(subsets)\n",
    "end_time = time.time()\n",
    "print(\"All frequent subsets:\", freq_sets)\n",
    "print(\"Time used for mining:\", end_time - start_time, \"seconds.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "含有一个商品的频繁集 [['butter'], ['bread'], ['milk']]\n",
      "含有两个商品的频繁集 [['bread', 'milk'], ['milk', 'bread']]\n",
      "含有三个商品的频繁集 []\n",
      "All frequent subsets: [['butter'], ['bread'], ['milk'], ['bread', 'milk'], ['milk', 'bread']]\n",
      "Time used for mining: 0.0021309852600097656 seconds.\n"
     ]
    }
   ],
   "source": [
    "# 张子豪\n",
    "# 任务五 实现Apriori算法\n",
    "sup = 0.3\n",
    "freq_sets = []\n",
    "item_list = ['butter', 'beer', 'bread', 'milk', 'diapers']\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "# 寻找含有一个商品的频繁集\n",
    "freq_sets1 = []\n",
    "freq_sets2 = []\n",
    "freq_sets3 = []\n",
    "freq_sets4 = []\n",
    "freq_sets5 = []\n",
    "for each in item_list:\n",
    "    each_list = each.split(',')\n",
    "    freq = support(each_list, transactions)\n",
    "    if freq > sup: \n",
    "        freq_sets1.append(each_list)\n",
    "        freq_sets.append(each_list)\n",
    "print('含有一个商品的频繁集',freq_sets1)\n",
    "\n",
    "# 在上一步的基础上寻找含有两个商品的频繁集\n",
    "for A_item in freq_sets1:\n",
    "    for B_item in freq_sets1:\n",
    "        if A_item == B_item:\n",
    "            pass\n",
    "        else:\n",
    "            each_list = A_item + B_item\n",
    "            freq = support(each_list, transactions)\n",
    "            if freq > sup: \n",
    "                freq_sets2.append(each_list)\n",
    "                freq_sets.append(each_list)\n",
    "print('含有两个商品的频繁集',freq_sets2)\n",
    "\n",
    "# 在上两步的基础上寻找含有三个商品的频繁集\n",
    "for A_item in freq_sets1:\n",
    "    for B_item in freq_sets2:\n",
    "        if A_item[0] in B_item:\n",
    "            pass\n",
    "        else:\n",
    "            each_list = A_item + B_item\n",
    "            freq = support(each_list, transactions)\n",
    "            if freq > sup: \n",
    "                freq_sets3.append(each_list)\n",
    "                freq_sets.append(each_list)\n",
    "print('含有三个商品的频繁集',freq_sets3)\n",
    "\n",
    "# 含有三个商品的频繁集为空集，不再继续生成新的频繁集\n",
    "\n",
    "end_time = time.time()\n",
    "print(\"All frequent subsets:\", freq_sets)\n",
    "print(\"Time used for mining:\", end_time - start_time, \"seconds.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
